#pragma once


namespace zhiang_key
{
	template<class K>
	struct BSTreeNode
	{
		K _val;
		BSTreeNode* _left;
		BSTreeNode* _right;
		BSTreeNode(const K& val) :_val(val), _left(nullptr), _right(nullptr) { }
	};

	template<class K>
	class BSTree
	{
	private:
		BSTreeNode<K>* _root;
		typedef BSTreeNode<K> Node;
	public:
		BSTree() : _root(nullptr) { }

		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node (key);
				return 1;
			}

			Node* cur = _root, * prev = nullptr;
			while (cur)
			{
				int num = cur->_val;
				if (num > key)
				{
					prev = cur;
					cur = cur->_left;
				}
				else if (num < key)
				{
					prev = cur;
					cur = cur->_right;
				}
				else return 0;
			}

			if (prev->_val > key) prev->_left = new Node(key);
			else prev->_right = new Node(key);

			return 1;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		bool Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				int num = cur->_val;
				if (num == key) return 1;
				else if (key < num) cur = cur->_left;
				else cur = cur->_right;
			}
			return 0;
		}

		bool Empty()
		{
			return _root == nullptr;
		}

		void Erase(const K& key)
		{
			Node* Parent = nullptr, * cur = _root;
			while (cur)
			{
				if (cur->_val > key)
				{
					Parent = cur;
					cur = cur->_left;
				}
				else if (cur->_val < key)
				{
					Parent = cur;
					cur = cur->_right;
				}
				else break;
			}

			if (cur == nullptr) return;
			if (cur->_left == nullptr)
			{
				if (Parent == nullptr)
				{
					_root = cur->_right;
					delete cur;
					return;
				}
				if (Parent->_left == cur) Parent->_left = cur->_right;
				else Parent->_right = cur->_right;
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (Parent == nullptr)
				{
					_root = cur->_left;
					delete cur;
					return;
				}
				if (Parent->_left == cur) Parent->_left = cur->_left;
				else Parent->_right = cur->_left;
				delete cur;
			}
			else
			{
				Node* LeftMax = cur->_left, * LeftMaxParent = cur;
				while (LeftMax->_right)
				{
					LeftMaxParent = LeftMax;
					LeftMax = LeftMax->_right;
				}
				if (LeftMaxParent == cur)
				{
					LeftMaxParent->_left = LeftMax->_left;
					swap(cur->_val, LeftMax->_val);
				}
				else
				{
					LeftMaxParent->_right = LeftMax->_left;
					swap(cur->_val, LeftMax->_val);
				}
				delete LeftMax;
			}
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;

			//while (!Empty())
			//{
			//	Erase(_root->_val);
			//}
		}

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_left);
			cout << root->_val << " -> ";
			_InOrder(root->_right);
		}
		void Destroy(Node* root)
		{
			if (root == nullptr) return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}
	};

}
 

namespace zhiang_kv
{
	template<class K, class V>
	struct BSTreeNode
	{
		K _key;
		V _val;
		BSTreeNode* _left;
		BSTreeNode* _right;
		BSTreeNode(const K& key, const V& val) :_key(key), _left(nullptr), _right(nullptr), _val(val) { }
	};

	template<class K, class V>
	class BSTree
	{
	private:
		BSTreeNode<K, V>* _root;
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree() : _root(nullptr) { }

		bool Insert(const K& key, const V& val)
		{
			if (_root == nullptr)
			{
				_root = new Node (key, val);
				return 1;
			}

			Node* cur = _root, * prev = nullptr;
			while (cur)
			{
				K& num = cur->_key;
				if (num > key)
				{
					prev = cur;
					cur = cur->_left;
				}
				else if (num < key)
				{
					prev = cur;
					cur = cur->_right;
				}
				else return 0;
			}

			if (prev->_key > key) prev->_left = new Node(key, val);
			else prev->_right = new Node(key, val);

			return 1;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				K& num = cur->_key;
				if (num == key) return cur;
				else if (key < num) cur = cur->_left;
				else cur = cur->_right;
			}
			return nullptr;
		}

		bool Empty()
		{
			return _root == nullptr;
		}

		void Erase(const K& key)
		{
			Node* Parent = nullptr, * cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					Parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					Parent = cur;
					cur = cur->_right;
				}
				else break;
			}

			if (cur == nullptr) return;
			if (cur->_left == nullptr)
			{
				if (Parent == nullptr)
				{
					_root = cur->_right;
					delete cur;
					return;
				}
				if (Parent->_left == cur) Parent->_left = cur->_right;
				else Parent->_right = cur->_right;
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (Parent == nullptr)
				{
					_root = cur->_left;
					delete cur;
					return;
				}
				if (Parent->_left == cur) Parent->_left = cur->_left;
				else Parent->_right = cur->_left;
				delete cur;
			}
			else
			{
				Node* LeftMax = cur->_left, * LeftMaxParent = cur;
				while (LeftMax->_right)
				{
					LeftMaxParent = LeftMax;
					LeftMax = LeftMax->_right;
				}
				if (LeftMaxParent == cur)
				{
					LeftMaxParent->_left = LeftMax->_left;
					swap(cur->_key, LeftMax->_key);
				}
				else
				{
					LeftMaxParent->_right = LeftMax->_left;
					swap(cur->_key, LeftMax->_key);
				}
				delete LeftMax;
			}
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;

			//while (!Empty())
			//{
			//	Erase(_root->_key);
			//}
		}

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_left);
			cout << root->_key << " -> "<< root->_val << endl;
			_InOrder(root->_right);
		}
		void Destroy(Node* root)
		{
			if (root == nullptr) return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}
	};

}
 